package com.soft.javase.ch09.set;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author wangzhisen
 * @Desc TODO
 * @date 2025/5/4
 *
 * Set 接口   -   Map<K,V> key键对应的就是Set
 * 1.存取顺序不一致
 * 2.不允许重复存放元素
 *
 * HashSet 实现类
 * 1.存取顺序不一致
 * 2.不允许重复存放元素，根据equals()和hashCode()
 * 3.线程不安全
 * 4.允许存放null值
 * 5.数据结构
 *     5.1 JDK1.8 之前 “数组+链表”
 *     5.2 JDK1.8 之后 “数组+链表+红黑树”
 *
 * 思考的问题：
 *  1.HashSet 怎么出现无序的情况的？
 *      底层计算hash值时，通过(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);计算
 *      计算对应添加元素的的“桶”数组的下标，通过(n - 1) & hash计算。
 *
 *  2.HashSet 如何保证元素的唯一性？
 *      根据hashcode()和equals()保证元素的唯一性。
 *      当hashcode一致时，equals不一定一致，需要查看equals是否一致，
 *              若equals一致，则认定为相同元素；
 *              若equals不一致，则认定为不同元素；
 *      当equals一致时，hashcode一定一致，直接认定是相同元素。
 *
 *  3.JDK8版本前后，底层存储结构有什么不同？为什么做出改变？
 *      1).底层是由数组 - 链表组成，当添加新元素时，它会根据元素的hash值找到对应的"桶"，也就是HashMap源码中Node<K, V> 里的元素，
 *  并插入到对应位置的链表中，链表元素个数过长时会转化为红黑树(JDK1.8后的版本)。
 *      2).链表取元素是从头结点一直遍历到对应的结点，这个过程的复杂度是O(N) ，而红黑树基于二叉树的结构，查找元素的复杂度为O(logN) ，
 *  所以，当元素个数过多时，用红黑树存储可以提高搜索的效率。
 *
 *  4.既然红黑树的效率高，那怎么不一开始就用红黑树存储呢？
 *      红黑树虽然查询效率比链表高，但是结点占用的空间大，只有达到一定的数目才有树化的意义，这是基于时间和空间的平衡考虑。
 *      此处翻译源代码注释：单个 TreeNode 需要占用的空间大约是普通Node的两倍，所以只有当包含足够多的Nodes时才会转成 TreeNodes，
 *  这个足够多的标准就是由 TREEIFY_THRESHOLD 的值（默认值8）决定的。而当桶中节点数由于移除或者 resize (扩容) 变少后，
 *  红黑树会转变为普通的链表，这个阈值是 UNTREEIFY_THRESHOLD（默认值6）。
 *
 *  5.为什么树化标准是8个？
 *      此处翻译源代码注释：如果hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。
 *  在理想情况下，链表长度符合“泊松分布”，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，
 *  概率概率仅为0.00000006，这么小的概率，HashMap的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据。
 *      若用户使用HashMap过程导致hashCode分布离散很差的场景（思考一下是什么场景），这个时候再转换为红黑树就是一种很好的退让策略。
 *  可以避免查询效率低下的问题，从而有效防止用户自己实现了不好的哈希算法时导致链表过长的情况。
 *
 *  6.底层计算hash值时，为什么要(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);这样运算？
 *      传入key之后，hash()会获取key的hashCode进行无符号右移 16 位，然后进行按位异或，并把运算后的值返回，这个值就是key的哈希值。
 *  这样运算是为了减少碰撞冲突，因为大部分元素的hashCode在低位是相同的，不做处理的话很容易造成冲突。
 *
 *  7.如何计算对应添加元素的的“桶”数组的下标？
 *      tab[i = (n - 1) & hash]) 当查找不到对应的索引时，就会新建一个新的结点作为链表的头结点。
 *  通过位运算，在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，
 *  之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开，达到较好的分布离散效果。
 *
 *  8.为什么退化为链表的阈值是6？
 *      当链表长度达到阈值8的时候会转为红黑树，但是红黑树退化为链表的阈值却是6。主要是一个过渡，避免链表和红黑树之间频繁的转换。
 * 如果阈值是7的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，
 * 所以阈值才不设置的那么临界。
 *
 * 9.默认加载因子是多少？什么是加载因子？
 * HashSet的默认加载因子0.75。
 * 加载因子 = 填入哈希表中的数据个数 / 哈希表的长度 ， 等价于 16 * 0.75 = 12 。
 * 加载因子的意义：
 *      加载因子越小，填满的数据就越少，哈希冲突的几率就减少，但是浪费了空间，而且还会提高扩容发生的几率；
 *      加载因子越大，填满的数据就越多，空间利用率越高，但是哈希冲突的几率就变大。
 *
 *  10.通过构造方法创建对象时，HashMap<E,Object> map = new HashMap();为何添加Object类型的PRESENT作为value？
 *  public boolean add(E e) {
 *     return map.put(e, PRESENT)==null;   //Object PRESENT = new Object();
 *  }
 *  HashSet添加元素add(E e)时，本质上HashMap的put(e,PRESENT)，此处使用PRESENT即new Object()，
 *  为了更准确得到remove(E e)移除后的结果，希望返回true则代表移除成功，返回false则代表移除失败。
 *  public boolean remove(Object o) { return map.remove(o)==PRESENT; }
 *
 */
public class HashSetDemo {

    public static void main(String[] args) {

        //add(E e) -> map.put(e, PRESENT) -> PRESENT(new Object())
        //remove(o) -> map.remove(o)==PRESENT 返回true则移除成功，返回false则移除失败

        HashSet<A> set = new HashSet();
        A a = new A();
        A b = new A();
        //添加
        set.add(a);
        set.add(b);
        //移除
        System.out.println(set.remove(a));//true
        System.out.println(set.remove(a));//false
        System.out.println(set);
        System.out.println(set.size());

        System.out.println("--------------MyHashSet--------------");
        MyHashSet<A> mySet = new MyHashSet<>();
        A c = new A();
        A d = new A();
        //添加元素
        mySet.add(c);
        mySet.add(d);
        System.out.println(mySet);
        System.out.println(mySet.size());
        //移除元素
        System.out.println(mySet.remove(c));//true
        System.out.println(mySet.remove(c));//true
        System.out.println(mySet.size());
    }
}
class A{

}
//自定义HashSet集合
class MyHashSet<T>{

    private HashMap<T,Object> map;

    public MyHashSet(){
        map = new HashMap<>();
    }

    //添加
    public boolean add(T e) {
        return map.put(e, null)==null;
    }

    //移除
    public boolean remove(Object o) {
        return map.remove(o)==null;
    }

    //获取长度
    public int size() {
        return map.size();
    }
}
